'''
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

'''
class Node:
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class LinkNode:
    def __init__(self,node=None):
        self.__head = node

    def is_empty(self):
        if self.__head == None:
            return True
        return False
    def len_(self):
        if not self.is_empty():
            cur = self.__head
            count = 1
            while cur.next:
                count+=1
                cur = cur.next
            return count
        return 0
    def append(self,elem):
        '''
        :param elem: 节点的值
        :return:
        '''
        if self.is_empty():
            node = Node(elem)
            self.__head = node
        else:
            cur = self.__head
            while cur.next:
                cur = cur.next
            node = Node(elem)
            cur.next = node
    def display(self):
        cur = self.__head
        if self.is_empty():
            print("链表为空！！！")
        else:
            while cur:
                print(cur.elem,sep='',end=" ")
                cur = cur.next
    def mergelink(self,linknode):
        '''
        :param linknode:
        :return: 在两个需要合并的列表中进行操作
        '''
        if self.is_empty():
            return linknode1
        elif linknode.is_empty():
            return self
        else:
            cur_1 = self.__head
            cur_2 = linknode.__head
            while cur_2 :
                if cur_1.elem <= cur_2.elem:
                    node = Node(cur_2.elem)
                    if cur_1.next.elem<cur_2.elem:
                        cur_1 = cur_1.next
                    node.next = cur_1.next
                    cur_1.next = node
                    cur_1 = cur_1.next
                    if cur_1.next==None:
                        cur_1.next = cur_2
                        break
                    else:
                        cur_2 = cur_2.next
                else:
                    node = Node(cur_2.elem)
                    node.next = cur_1
                    self.__head = node
                    cur_2 = cur_2.next
                    cur_1 = self.__head
            self.display()
if __name__=="__main__":
    linknode1 = LinkNode()
    list_1 = sorted([1,2,4])
    for i in range(len(list_1)):
        linknode1.append(list_1[i])
    linknode1.display()
    print("")
    linknode2 = LinkNode()
    list_2 = sorted([1,3,4])
    for i in range(len(list_2)):
        linknode2.append(list_2[i])
    linknode2.display()
    print("*"*30)
    linknode1.mergelink(linknode2)







